import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;


public class TestHeap {
    private int[] elem;  //建立数组
    private int usedSize;

    public TestHeap(){
        this.elem = new int[10];
    }
    public void initHeap(int[] array){
        for (int i = 0; i < elem.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }
    public void createHeap(){  //创建大根堆\
        for (int parent = (usedSize-1-1)/2 ; parent >= 0 ; parent--){
            shiftDown(parent,usedSize);
        }
    }
    private void shiftDown(int parent,int usedSize){
        int child = (2*parent)+1;//左孩子的下标
        while (child < usedSize){
            if (child+1 < usedSize && elem[child] < elem[child+1]){//选出孩子中较大的那个
                child++;
            }
            if (elem[parent] < elem[child]){
                change(parent,child);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }
    private void change(int i,int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }




    public void offer(int val){ //在大根堆中插入一个数
        if (isFull()){
            this.elem = Arrays.copyOf(elem,2*elem.length);//扩容
        }
        this.elem[usedSize] = val;//将插入进来的值放在数组的最后一位
        //向上调整
        shiftUp(usedSize);
        usedSize++;
    }
    public void shiftUp(int child){  //将大根堆进行调整
        int parent = (child-1)/2; //寻找该节点的父节点
        while (child > 0){
            if (elem[child] > elem[parent]){
                change(parent,child);
                child = parent;  //将调整过后的parent放到调整后的父节点上
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull(){
        return usedSize == elem.length;
    }



    public int poll(int val){  //删除顶元素
        int tmp = elem[0];
        change(elem[0],elem[usedSize]);//将顶元素和末尾元素进行交换
        usedSize--;
        shiftDown(elem[0],usedSize);
        return tmp;
    }
    public int[] smallestK1(int[] arr, int k) {//取出最小的K个数
        int[] ret = new int[k];
        if (arr == null || k <= 0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arr.length);
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[] tmp = new int[k];
        for (int j = 0; j < k; j++) {
            tmp[j] = priorityQueue.poll();
        }
        return tmp;
    }

    public int[] biggestK(int[] arr, int k) {  //取出最大的K个数
        int[] ret = new int[k];
        if (arr == null || k <= 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int top = priorityQueue.peek();
            if (arr[i] > top) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        int[] tmp = new int[k];
        for (int j = 0; j < k; j++) {
            tmp[j] = priorityQueue.poll();
        }
        return tmp;
    }
    class InrCmp implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);  //o2-o1
        }
    }
    public int[] smallestK(int[] arr, int k) {  //取出最小的K个数
        int[] ret = new int[k];
        if (arr == null || k <= 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new InrCmp());
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int top = priorityQueue.peek();
            if (arr[i] < top) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }
        int[] tmp = new int[k];
        for (int j = 0; j < k; j++) {
            tmp[j] = priorityQueue.poll();
        }
        return tmp;
    }
}
